package com.hdu.other.binarySearch;

import java.util.Arrays;

public class lc410 {
    class Solution {
        public int splitArray(int[] nums, int k) {
            int l = 0, r = Arrays.stream(nums).sum(), ans = 0;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (f(nums, mid) <= k) {
                    ans = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            return ans;
        }

        int f(int[] nums, int limit) {
            int parts = 1;
            int sum = 0;
            for (int num : nums) {
                if (num > limit) {
                    return Integer.MAX_VALUE;
                } else if (num + sum > limit) {
                    parts++;
                    sum = num;
                } else {
                    sum += num;
                }
            }
            return parts;
        }
    }
}
